Leetcode 300.最长递增子序列

题目描述：

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

进阶：

• 你可以设计时间复杂度为 $O(n^2)$ 的解决方案吗？
• 你能将算法的时间复杂度降低到 $O(n\log(n))$ 吗?

示例 1：

1
2
3

输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。

示例 2：

1
2

输入：nums = [0,1,0,3,2,3]
输出：4

示例 3：

1
2

输入：nums = [7,7,7,7,7,7,7]
输出：1

提示：

• $1 <= nums.length <= 2500$
• $-10^4 <= nums[i] <= 10^4$

链接：

https://leetcode-cn.com/problems/longest-increasing-subsequence

题目分析

1.动态规划

  我们思考子序列之间的联系，如果 nums[j] 是递增子序列中的最后一个数，则我们只需要满足 nums[i] > nums[j] 且其中 i > j，则 nums[i] 可以接在以 nums[j] 后面成为更长的递增子序列，这样的关联是满足动态规划性质的。而对于每个 i，满足这样关系的 j 可以是多个的，我们需要找到最长的那一个。
  我们定义 dp[i] 为以 nums[i] 为结尾的最长递增子序列。那么我们有状态转移方程：$dp[i]=max(dp[j])+1$，其中 $0\leq j < i$ 且 $nums[j]< nums[i]$。最短的递增子序列就只包含本身，长度为 1，因此我们将所有的初始状态赋值为 1。对于每个状态，我们都需要遍历前面所有的状态找到最大值，需要进行双层遍历，满足第一个进阶要求。而我们所要求的结果就是这个过程中出现的最大状态值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int maxdp = 1;
        vector<int> dp(nums.size(), 1);
        for(int i = 1; i < nums.size(); i++){
            for(int j = 0; j < i; j++){
                if(nums[j] < nums[i]){
                    dp[i] = max(dp[i], dp[j]+1);
                }
            }
            maxdp = max(maxdp, dp[i]);
        }
        return maxdp;
    }
};

  时间复杂度：$O(n^2)$，其中 $n$ 是数组的大小。每一个状态依赖于前面的所有状态，需要进行双层遍历。
  空间复杂度：$O(n)$，其中 $n$ 是数组的大小。我们需要一个数组保存所有的状态，状态数为 $n$。

2.贪心+二分 - 官方题解

  这个解法我没有想出来，看了官方题解之后看懂了，在这里用我的话重述。对于同样长度的递增子序列，哪一个是更优的？应该是最后一个数更小的那一个，因为它提供了下一个数更多的可能，换句话说，让序列上升的“慢一些”。那我们使用 greed[i] 表示长度为 i 的递增子序列中最小的末尾元素。这个数组是单调递增的。为什么呢？
  我们采用反证法，假设存在 i > j 使得 greed[i] < greed[j]，那么在长度为 i 的子序列 A 中，前 j 个数也可以构成一个递增子序列 B，并且这个长度为 j 的子序列 B 的末尾元素一定小于 greed[i]（因为它就包含在 A 中），那么就与 greed[i] < greed[j] 矛盾了。
  这个数组是单调的有什么好处？单调的数组进行搜索的时候就可以使用二分法了。如何对这个数组进行更新呢？我们顺序遍历原数组，假设我们遍历到的数比 greed 的最后一个元素大，这意味着这个数可以构成更长的递增子序列，则我们将其添加到 greed 之后，表示新的最长长度子序列以这个数结尾。
  如果遍历到的数 nums[i] 不比 greed 最后一个元素大，思考一下对 greed 数组中的数的影响。假设 greed[0 ~ k] 是小于 nums[i] 的所有数，则对于这些数来说没有影响，因为我们本来就要让 greed 值尽可能小。而对于 greed[k+1]，这个时候我们可以用 greed[k] 代表的 k 个数加上 nums[i] 组成一个长度为 k+1 的递增子序列，也即 greed[k+1] 的值可以更新为 nums[i]。对于后面的所有数，由于 greed[k+1 ~ n] >= nums[i]，则 nums[i] 对它们也没有影响。
  通过上面的分析，我们可以知道 nums[i] 只需要对单调数组 greed 中的第一个不小于它的值进行替换，则可以使用二分法搜索。这样也达到了我们第二个进阶要求中的对数复杂度。
  最后的答案就是 greed 数组的最大下标，而且 greed[0] 是没有作用的，我们可以直接全体前移一位，greed[i] 表示长度为 i+1 的递增子序列中最小的末尾元素。那么答案就刚好是 greed 数组的大小。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        vector<int> greed(1, nums[0]);
        for(int i = 1; i < nums.size(); i++){
            if(nums[i] > greed.back()){
                greed.push_back(nums[i]);
            }
            else{
                int left = 0, right = greed.size()-1, pos = 0;
                while(left < right){
                    int mid = (left + right) >> 1;
                    if(greed[mid] < nums[i]){
                        left = mid + 1;
                    }
                    else{
                        right = mid;
                    }
                }
                greed[left] = nums[i];
            }
        }
        return greed.size();
    }
};

  时间复杂度：$O(n\log n)$，其中 $n$ 是数组的大小。我们遍历了数组对 greed 进行更新，而每次更新操作的时间复杂度为 $O(1)$（插入最后）或者 $O(\log n)$（二分法更新中间值）。
  空间复杂度：$O(n)$，其中 $n$ 是数组的大小。我们需要一个 greed 数组，最大长度为 $n$。

  PS：感觉还是讲不清楚第二种方法，重点在于理解 greed 数组中每个数所代表的含义（千万注意 greed 并不代表最终的递增子序列），应该就可以明白为什么只需要更新不小于 nums[i] 的第一个值了。